package com.demo.solution;

import java.util.Arrays;

public class Solution1 {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        char[] ary = new char[2 * s.length() + 1];
        Arrays.fill(ary, '$');
        for (int i = 0; i < s.length(); i++) {
            ary[2 * i + 1] = s.charAt(i);
        }

        int[] len = new int[ary.length];
        len[0] = 1;
        int minLen = 1;
        int maxLen = 1;
        int center = 1;
        for (int i = 1; i < ary.length; i++) {
            minLen = getMinLen(ary, len, i);
            len[i] = getLength(ary, i, minLen);
            if (len[i] > maxLen) {
                maxLen = len[i];
                center = i;
            }
        }

        StringBuilder str = new StringBuilder();
        System.out.println(center - maxLen / 2);
        for (int i = center - maxLen / 2; i < center - maxLen / 2 + maxLen; i++) {
            if (ary[i] != '$') {
                str.append(ary[i]);
            }
        }

        return new String(str);
    }

    private static int getMinLen(char[] ary, int[] len, int index) {
        int start = index - 1;
        int minLen = 1;
        while (2 * start > index) {
            if (len[start] > 2 * (index - start) + 1) {
                int tmp = len[2 * start - index];
                int maxValid = len[start] - 2 * (index - start);
                if (maxValid > tmp) {
                    maxValid = tmp;
                }
                if (minLen > maxValid) {
                    minLen = maxValid;
                }
            }
            start--;
        }
        return minLen;
    }

    private static int getLength(char[] ary, int index, int minLen) {
        int start = (1 + minLen) / 2;
        int len = minLen;
        while (index - start >= 0 && index + start < ary.length) {
            if (ary[index - start] == ary[index + start]) {
                start += 1;
                len += 2;
            } else {
                break;
            }
        }
        return len;
    }

    public static void main(String[] args) {
        String str = "abba3434t6wsdfgztgghhggtzxcbxnvdrt5y45";
        String s = new Solution1().longestPalindrome(str);
        System.out.println("s = " + s);
    }
}